Search results for "Graph automorphism"

showing 2 items of 2 documents

Graph Connectivity, Monadic NP and built-in relations of moderate degree

1995

It has been conjectured [FSV93] that an existential secondoder formula, in which the second-order quantification is restricted to unary relations (i.e. a Monadic NP formula), cannot express Graph Connectivity even in the presence of arbitrary built-in relations.

Discrete mathematicsVoltage graphlaw.inventionCombinatoricsMathematics::LogiclawComputer Science::Logic in Computer ScienceClique-widthLine graphRegular graphGraph automorphismNull graphComputer Science::Formal Languages and Automata TheoryConnectivityComplement graphMathematics
researchProduct

Automorphisms and abstract commensurators of 2-dimensional Artin groups

2004

In this paper we consider the class of 2-dimensional Artin groups with connected, large type, triangle-free defining graphs (type CLTTF). We classify these groups up to isomorphism, and describe a generating set for the automorphism group of each such Artin group. In the case where the defining graph has no separating edge or vertex we show that the Artin group is not abstractly commensurable to any other CLTTF Artin group. If, moreover, the defining graph satisfies a further `vertex rigidity' condition, then the abstract commensurator group of the Artin group is isomorphic to its automorphism group and generated by inner automorphisms, graph automorphisms (induced from automorphisms of the…

Vertex (graph theory)20F67CommensuratorCoxeter groupCoxeter group20F36InverseGroup Theory (math.GR)Automorphism2–dimensional Artin group20F36 20F55 20F65 20F67CombinatoricsMathematics::Group Theorytriangle freeGenerating set of a groupFOS: Mathematicscommensurator groupArtin groupGeometry and TopologyIsomorphism20F5520F65graph automorphismsMathematics - Group TheoryMathematics
researchProduct